//N 对情侣坐在连续排列的 2N 个座位上，想要牵到对方的手。 计算最少交换座位的次数，以便每对情侣可以并肩坐在一起。 一次交换可选择任意两人，让他们站起来交
//换座位。 
//
// 人和座位用 0 到 2N-1 的整数表示，情侣们按顺序编号，第一对是 (0, 1)，第二对是 (2, 3)，以此类推，最后一对是 (2N-2, 2N-1)
//。 
//
// 这些情侣的初始座位 row[i] 是由最初始坐在第 i 个座位上的人决定的。 
//
// 示例 1: 
//
// 
//输入: row = [0, 2, 1, 3]
//输出: 1
//解释: 我们只需要交换row[1]和row[2]的位置即可。
// 
//
// 示例 2: 
//
// 
//输入: row = [3, 2, 0, 1]
//输出: 0
//解释: 无需交换座位，所有的情侣都已经可以手牵手了。
// 
//
// 说明: 
//
// 
// len(row) 是偶数且数值在 [4, 60]范围内。 
// 可以保证row 是序列 0...len(row)-1 的一个全排列。 
// 
// Related Topics 贪心算法 并查集 图 
// 👍 112 👎 0

package com.leetcode.editor.cn;

//Java：情侣牵手
class P765CouplesHoldingHands {
    public static void main(String[] args) {
        Solution solution = new P765CouplesHoldingHands().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int minSwapsCouples(int[] row) {
            //存放每个人对应的位置索引
            int[] sites = new int[row.length];
            for (int i = 0; i < row.length; i++) {
                sites[row[i]] = i;
            }
            int count = 0;
            for (int i = 0; i < row.length; i += 2) {
                int A = row[i];
                int B = A % 2 == 0 ? A + 1 : A - 1;
                if (row[i + 1] == B) {
                    continue;
                }
                //情侣B所在的位置
                int bIndex = sites[B];
                //交换i+1和bIndex的值
                row[bIndex] = row[i + 1];
                row[i + 1] = B;
                //  i+1 元素移动到了 B 原来的位置，应同步更新到 sites
                sites[row[bIndex]] = bIndex;
                count++;
            }
            return count;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}